package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 剑指 Offer II 086. 分割回文子字符串
 *
 * @Author liw
 * @Date 2021/4/21 9:25
 * @Version 1.0
 */
public class Partition {
    public static void main(String[] args) {
        // [,,,["aa","b","b","a","a"],["aa","b","b","aa"],["aa","bb","a","a"],]
        // [, [aa, b, b, a, a], , [aa, bb, a, a],   [aa, b, b, aa],   ]
        List<List<String>> partition = new Partition().partition3("aabbaa");
        System.out.println(partition);
    }


    public String[][] partition(String s) {
        List<List<String>> all = new ArrayList<>();
        int length = s.length();
        List<String> list = new ArrayList<>();
        list.add(s.substring(0, 1));
        all.add(list);
        for (int i = 1; i < length; i++) {
            String str = String.valueOf(s.charAt(i));
            List<List<String>> copy = new ArrayList<>();
            for (List<String> a : all) {
                int size = a.size();
                String last1 = a.get(size - 1);
                if (last1.equals(str)) {
                    list = copy(a, size - 1);
                    list.add(str + str);
                    copy.add(list);
                }
                if (size > 1) {
                    String last2 = a.get(size - 2);
                    if (last2.equals(str)) {
                        list = copy(a, size - 2);
                        list.add(str + last1 + str);
                        copy.add(list);
                    }
                }
                a.add(str);
            }
            all.addAll(copy);
        }
        int m = all.size();
        String[][] arr = new String[m][];
        for (int i = 0; i < m; i++) {
            List<String> li = all.get(i);
            int n = li.size();
            arr[i] = new String[n];
            String[] ints = arr[i];
            for (int j = 0; j < n; j++) {
                ints[j] = li.get(j);
            }
        }
        return arr;
    }


    public List<List<String>> partition3(String s) {
        List<List<String>> all = new ArrayList<>();
        int length = s.length();
        List<String> list = new ArrayList<>();
        list.add(s.substring(0, 1));
        all.add(list);
        for (int i = 1; i < length; i++) {
            String str = String.valueOf(s.charAt(i));
            List<List<String>> copy = new ArrayList<>();
            for (List<String> a : all) {
                int size = a.size();
                String last1 = a.get(size - 1);
                if (last1.equals(str)) {
                    list = copy(a, size - 1);
                    list.add(str + str);
                    copy.add(list);
                }
                if (size > 1) {
                    String last2 = a.get(size - 2);
                    if (last2.equals(str)) {
                        list = copy(a, size - 2);
                        list.add(str + last1 + str);
                        copy.add(list);
                    }
                }
                a.add(str);
            }
            all.addAll(copy);
        }

        return all;
    }

    public List<List<String>> partition2(String s) {
        List<List<String>> all = new ArrayList<>();
        int length = s.length();
        List<String> list = new ArrayList<>();
        list.add(s.substring(0, 1));
        all.add(list);
        for (int i = 1; i < length; i++) {
            String str = String.valueOf(s.charAt(i));
            List<List<String>> copy = new ArrayList<>();
            for (List<String> a : all) {
                int size = a.size();
                String last1 = a.get(size - 1);
                if (last1.equals(str)) {
                    list = copy(a, size - 1);
                    list.add(str + str);
                    copy.add(list);
                }
                if (size > 1) {
                    String last2 = a.get(size - 2);
                    if (last2.equals(str)) {
                        list = copy(a, size - 2);
                        list.add(str + last1 + str);
                        copy.add(list);
                    }
                }
                a.add(str);
            }
            all.addAll(copy);
        }
        return all;
    }

    private static List<String> copy(List<String> list, int limit) {
        List<String> other = new ArrayList<>(limit + 1);
        for (int i = 0; i < limit; i++) {
            other.add(list.get(i));
        }
        return other;
    }

}
